package 单链表;

public class partition {

    //这是两个链表合并的逆向操作。将链表分成两个链表，一个链表的所有节点的值都小于x，另一个链表的所有节点的值都大于等于x
    public ListNode partition(ListNode head, int x) {

        ListNode dummy1=new ListNode(-1);
        ListNode p1=dummy1;

        ListNode dummy2=new ListNode(-1);
        ListNode p2=dummy2;

        ListNode cur=head;
        while (cur!=null){
            if (cur.val<x){
                p1.next=cur;
                p1=p1.next;
            }else{
                p2.next=cur;
                p2=p2.next;
            }
            cur=cur.next;
        }
        p1.next=dummy2.next;
        p2.next=null;
        return dummy1.next;
    }
}
